package vno.ky.seek
{
	import flash.display.Sprite;
	
	import flashx.textLayout.elements.BreakElement;
	import flashx.textLayout.factory.TruncationOptions;
	import flashx.textLayout.formats.Float;
	
	import vno.fux.BasePoint;
	import vno.fux.CompassDirection;
	
	public class Deal extends Sprite
	{
		private var StartX:int; 
		private var StartY:int;
		private var EndX:int;
		private var EndY:int;
		private var Road:Vector.<Vector.<RoadClass>>;
		private var lengthAll:int;
		private var length:Array=new Array();
		private var pointID:int;
		private var binaryTree:Array;
		private var storeinf:Array;
		function Deal()
		{
			
		}
		public function seek(startX:int,startY:int,endX:int,endY:int):Array									//开始寻找路径
		{
			binaryTree=new Array();
			storeinf=new Array();
			binaryTree[0]=0;										//第一个元素置0,以满足二叉树从1开始的条件
			pointID=0;
			var i:int;
			var j:int;
			StartX=startX;
			StartY=startY;
			EndX=endX;
			EndY=endY;
			for(i=0;i<lengthAll;i++)								//初始化路点属性
			{
				for(j=0;j<length[i];j++)
				{
					if(Road[i][j].Type!=2)
					{
						Road[i][j].Type=0;
					}
				}
			}
//			if(JudLine(StartX,StartY,EndX,EndY))													//判断两点之间是否是直线（无障碍）
//			{
//				var result:Array=new Array();							//*（修改）全局变量变为局部
//				result[0]=new TurnPoint(StartX,StartY);
//				result[1]=new TurnPoint(EndX,EndY);
//				return result;
//			}
			Road[StartX][StartY].Type=3;
			Road[StartX][StartY].GPoint=0;
			Road[StartX][StartY].HPoint=Math.abs(EndX-StartX)*10+Math.abs(EndY-StartY)*10;
			Road[StartX][StartY].FPoint=Road[StartX][StartY].HPoint;
			var TempX:int=StartX;
			var TempY:int=StartY;
			var TempG1:int;
			var TempG2:int;
			var LGPoint:int;
			var r:Boolean=true;												//使第一次循环能顺利进行（第一次循环时开放列表为空）
			while(((TempX==EndX&&TempY==EndY)==0)&&(((binaryTree.length!=1)||r)))		//结束循环条件：开放列表为空或已到达终点并且不是第一次执行循环
			{
//				var r:Boolean=false;				//确立变量r，以判断此节点是否为死节点（四周无开放列表或可通过节点）
				r=false;
				Road[TempX][TempY].Type=3;
				for(i=-1;i<=1;i++)					//遍历四周方格，确定父节点，G、H、F值，改变属性
				{
					for(j=-1;j<=1;j++)
					{
						if(TempX+i<0||TempY+j<0)		//越界
						{
							continue;
						}
						if(Road[TempX+i][TempY+j].Type==2||Road[TempX+i][TempY+j].Type==3)
						{
							continue;				//封闭列表或墙，跳过
						}
						else
						{
							TempG1=6+4*Math.abs(i)+4*Math.abs(j);
							if(Road[TempX+i][TempY+j].Type==1)					//属性为开放列表
							{
								TempG2=6+4*Math.abs(TempX+i-Road[TempX+i][TempY+j].LXPosition)+4*Math.abs(TempY+j-Road[TempX+i][TempY+j].LYPosition);
								if(openlist(TempX,TempY,TempG1,TempG2,i,j))
								{
									continue;
								}
							}
							if(Road[TempX+i][TempY+j].Type==0)									//不在开放列表，设置GHF值和父节点，加入开放列表
							{
								nolist(TempX,TempY,TempG1,TempG2,i,j);
							}
						}
					}
				}
				TempX=storeinf[binaryTree[1]].XPoint;
				TempY=storeinf[binaryTree[1]].YPoint;
				Road[TempX][TempY].Type=3;
				removeTree(1);															//删除数组第一个元素
/*				var minFPoint:int=Road[TempX][TempY].FPoint+100;
				var FminX:int;
				var FminY:int;
				if(r==false)													//当前节点为死节点
				{
					if(TempX==StartX&&TempY==StartY)
					{
						var result:Array=new Array();							//*（修改）全局变量变为局部
						trace("no path!");
						result[0]=new TurnPoint(StartX,StartY);
						result[1]=new TurnPoint(EndX,EndY);
						return result;
					}
					var k:int;
					var l:int;
					Road[TempX][TempY].Type=3;
					k=TempX;
					l=TempY;
					TempX=Road[k][l].LXPoint;
					TempY=Road[k][l].LYPoint;
					continue;
				}
				for(i=-1;i<=1;i++)											//再次遍历四周方格，找出F最小的坐标
				{
					for(j=-1;j<=1;j++)
					{
						if(TempX+i<0||TempY+j<0)
						{
							continue;
						}
						if(Road[TempX+i][TempY+j].Type==1)
						{
							if(Road[TempX+i][TempY+j].FPoint<minFPoint)
							{
								minFPoint=Road[TempX+i][TempY+j].FPoint;
								FminX=TempX+i;
								FminY=TempY+j;
							}
						}
					}
				}
				Road[TempX][TempY].Type=3;
				Road[FminX][FminY].LXPoint=TempX;
				Road[FminX][FminY].LYPoint=TempY;
				TempX=FminX;
				TempY=FminY;		*/
			}	
/////			return display(TempX,TempY);
			if(TempX==EndX&&TempY==EndY)
			{
//				delete binaryTree;										//删除树
//				delete storeinf;										//删除树结点与地图点的对应关系
				return display(TempX,TempY);
			}
			else
			{
				var result:Array=new Array();							//*（修改）全局变量变为局部
				trace("no path!");
				result[0]=new TurnPoint(StartX,StartY);
				result[1]=new TurnPoint(EndX,EndY);
//				delete binaryTree;										//删除树
//				delete storeinf;										//删除树结点与地图点的对应关系
				return result;
			}
		}
		public function set(sample:Vector.<Vector.<int>>):void						//初始化函数
		{
			var i:int;
			var j:int;
			Road=new Vector.<Vector.<RoadClass>>(sample.length+1, true);				//初始化坐标
			lengthAll=sample.length;
			for(i=0;i<lengthAll;i++)
			{
				length[i]=new int();
				length[i]=sample[i].length;
			}
			length[i]=sample[i-1].length;
			for(i=0;i<=lengthAll;i++)
			{
				Road[i]=new Vector.<RoadClass>(length[i]+1,true);
			}
			for(i=0;i<lengthAll;i++)
			{
				for(j=0;j<length[i];j++)
				{
					Road[i][j]=new RoadClass(i,j);				
				}
			}
			for(i=0;i<lengthAll;i++)
			{
				for(j=0;j<length[i];j++)
				{
					if(sample[i][j]==1)
					{
						Road[i][j].Type=2;
					}
					if(sample[i][j]==0||sample[i][j]==2)
					{
						Road[i][j].Type=0;
					}
					if(sample[i][j]<0)
					{
						trace("wrong road");
					}
				}
			}
			for(i=0;i<=lengthAll;i++)						//外部全加上墙
			{
				Road[i][sample[0].length]=new RoadClass(i,j);
				Road[i][sample[0].length].Type=2;
			}
			for(i=0;i<=sample[0].length;i++)
			{
				Road[sample.length][i]=new RoadClass(i,j);
				Road[sample.length][i].Type=2;
			}
		}
		private function openlist(TempX:int,TempY:int,TempG1:int,TempG2:int,i:int,j:int):Boolean				//开放列表处理
		{
			var LGPoint:int;
			LGPoint=Road[Road[TempX+i][TempY+j].LXPosition][Road[TempX+i][TempY+j].LYPosition].GPoint;		//父节点G值
			if((Road[TempX][TempY].GPoint+TempG1)>=(LGPoint+TempG2))									//原G值更小，跳过
			{
				return true;
			}	
			else															//现有G值更小，刷新GHF值，重设父节点
			{	
				Road[TempX+i][TempY+j].GPoint=Road[TempX][TempY].GPoint+TempG1;
				Road[TempX+i][TempY+j].ChangeFPoint();
				Road[TempX+i][TempY+j].LXPosition=TempX;
				Road[TempX+i][TempY+j].LYPosition=TempY;
				resetTree(searchTree(TempX+i,TempY+j),Road[TempX+i][TempY+j].FPoint);
				return false;
			}
		}
		private function nolist(TempX:int,TempY:int,TempG1:int,TempG2:int,i:int,j:int):void					//不在任何列表中的处理
		{
			Road[TempX+i][TempY+j].GPoint=Road[TempX][TempY].GPoint+TempG1;
			Road[TempX+i][TempY+j].HPoint=Math.abs(EndX-TempX-i)*10+Math.abs(EndY-TempY-j)*10;
			Road[TempX+i][TempY+j].ChangeFPoint();
			Road[TempX+i][TempY+j].LXPosition=TempX;
			Road[TempX+i][TempY+j].LYPosition=TempY;
			Road[TempX+i][TempY+j].Type=1;
			if(JudDir(TempX,TempY,TempX+i,TempY+j)==JudDir(Road[TempX][TempY].LXPosition,Road[TempX][TempY].LYPosition,TempX,TempY))//优化路径
			{
				Road[TempX+i][TempY+j].GPoint--;
				Road[TempX+i][TempY+j].ChangeFPoint();
			}
			joinOpenlist(TempX+i,TempY+j,Road[TempX+i][TempY+j].FPoint);
		}
		private function joinOpenlist(x:int,y:int,FPoint:int):void
		{
			storeinf[pointID]=new Sort(x,y,FPoint);					//获取pointID后，storeinf【pointID】即存储对应坐标和F值
			addTree(pointID);
			pointID++;
		}
		private function addTree(point:int):void
		{
			var length:int=binaryTree.length;
			binaryTree[length]=point;
			var r:Boolean=true;						//变量r的确立使第一次循环顺利执行
			while((length!=1)||r)
			{
				r=false;
				if(length%2==1)
				{
					var getint:int=(length-1)/2
				}
				else
				{
					getint=length/2;
				}
				if(storeinf[binaryTree[length]].FPoint<storeinf[binaryTree[getint]].FPoint)
				{
					var trans:int;
					trans=binaryTree[length];
					binaryTree[length]=binaryTree[getint];
					binaryTree[getint]=trans;
					length=getint;
				}
				else
				{
					break;
				}
			}
		}
		private function searchTree(x:int,y:int):int
		{
			for(var i:int=1;i<binaryTree.length;i++)
			{
				if(x==storeinf[binaryTree[i]].XPoint&&y==storeinf[binaryTree[i]].YPoint)
				{
					return i;
				}
			}
			return 0;
		}
		private function removeTree(ID:int):void
		{
			var length:int=binaryTree.length;
			var t:int=binaryTree[ID];
			binaryTree[ID]=binaryTree[length-1];
			binaryTree[length-1]=t;
			binaryTree.pop();
			while(2*ID<=length-2)
			{
				if(2*ID+1>length-2)
				{
					if(storeinf[binaryTree[ID]].FPoint>storeinf[binaryTree[2*ID]].FPoint)
					{
						t=binaryTree[ID];
						binaryTree[ID]=binaryTree[ID*2];
						binaryTree[ID*2]=t;
					}
					break;
				}
				else
				{
					if(storeinf[binaryTree[2*ID+1]].FPoint>storeinf[binaryTree[2*ID]].FPoint)
					{
						if(storeinf[binaryTree[ID]].FPoint>storeinf[binaryTree[2*ID]].FPoint)
						{
							t=binaryTree[ID];
							binaryTree[ID]=binaryTree[2*ID];
							binaryTree[2*ID]=t;
							ID=2*ID;
						}
						else
						{
							break;
						}
					}
					else
					{
						if(storeinf[binaryTree[ID]].FPoint>storeinf[binaryTree[2*ID+1]].FPoint)
						{
							t=binaryTree[ID];
							binaryTree[ID]=binaryTree[2*ID+1];
							binaryTree[2*ID+1]=t;
							ID=2*ID+1;
						}
						else
						{
							break;
						}
					}
				}
			}
		}
		private function resetTree(ID:int,point:int):void		//注：只允许修改的值比原来的小
		{
			storeinf[binaryTree[ID]].FPoint=point;
			while(ID!=1)
			{
				if(ID%2==1)
				{
					var getint:int=(ID-1)/2
				}
				else
				{
					getint=ID/2;
				}
				if(storeinf[binaryTree[ID]].FPoint<storeinf[binaryTree[getint]].FPoint)
				{
					var t:int=binaryTree[ID];
					binaryTree[ID]=binaryTree[getint];
					binaryTree[getint]=t;
					ID=getint;
				}
				else
				{
					break;
				}
			}
		}
		private function display(TempX:int,TempY:int):Array													//显示路径
		{
			var TemResult:Array=new Array();
			var DisplayX:Array=new Array();
			var DisplayY:Array=new Array();
			var i:int;
			var j:int;
			var k:int;
			var TempDir:String;
			var TempCount:Array=new Array();						//该数值为了保留路径拐点
			var result:Array=new Array();							//*（修改）全局变量变为局部
			DisplayX[0]=EndX;
			DisplayY[0]=EndY;
			for(i=1;(TempX==StartX&&TempY==StartY)==0;i++)				//沿父节点存储路径
			{
				DisplayX[i]=Road[TempX][TempY].LXPosition;
				DisplayY[i]=Road[TempX][TempY].LYPosition;
				TempX=DisplayX[i];
				TempY=DisplayY[i];
			}
			for(j=0,i--;i>=0;i--,j++)
			{
				TemResult[j]=new TurnPoint();
				TemResult[j].pathX=DisplayX[i];
				TemResult[j].pathY=DisplayY[i];
			}
			TempDir=JudDir(TemResult[0].pathX,TemResult[0].pathY,TemResult[1].pathX,TemResult[1].pathY);
			result[0]=new TurnPoint(StartX,StartY);
			return TemResult;				//供临时测试，输出所有节点
			for(i=0,k=1;i<j-1;i++)								//简化节点
			{
				var dir:String=JudDir(TemResult[i].pathX,TemResult[i].pathY,TemResult[i+1].pathX,TemResult[i+1].pathY);
				if(dir==TempDir)
				{
					continue;
				}
				else
				{
					result[k]=new TurnPoint(TemResult[i].pathX,TemResult[i].pathY);
					TempDir=dir;
					TempCount[k-1]=new int();
					TempCount[k-1]=i;
					k++;	
				}
			}
			result[k]=new TurnPoint(EndX,EndY);
			for(i=0;i<=result.length-3;i++)
			{
				if(JudLine(result[i].pathX,result[i].pathY,result[i+2].pathX,result[i+2].pathY))
				{
					result.splice(i+1,1);								//删除元素 
				}
			}
			return result;
		}
		private function JudLine(Sx:int,Sy:int,Ex:int,Ey:int):Boolean
		{
			var tempy:int;
			var nexty:int;
			var SxHighEx:Boolean=false;
			var SyHighEy:Boolean=false;
			var addy:int=1;
			var k:Number;			//直线斜率
			if(Sx>Ex)
				SxHighEx=true;
			if(Sy>Ey)
				SyHighEy=true;
			k=(Ey-Sy)/(Ex-Sx);
			if(SyHighEy)
				addy=-1;							//区分直线相对于y轴走向，变更add值
			tempy=Sy;
			nexty=(int)(Sy+k*(i-Sx))+addy;
			if(SxHighEx)							//区分直线相对于x轴的走向，变更相应的循环条件
			{
				for(var i:int=Sx-1;i>Ex;i--)
				{
					tempy=(int)(Sy+k*(i-Sx));
					for(var j:int =i;j<=i+1;j++)						//将当前横坐标和上一个横坐标围城的矩形间的点遍历
					if(Road[i][tempy].Type==2&&Road[i][tempy+addy].Type==2)
					{
						return false;
					}
				}
			}
			else
			{
				for(i=Sx+1;i<Ex;i++)
				{
					tempy=(int)(Sy+k*(i-Sx));
					if(Road[i][tempy].Type==2&&Road[i][tempy+addy].Type==2)
					{
						return false;
					}
				}
			}
			return true;
		}	
		private function JudDir(XPosition:int,YPosition:int,NXPosition:int,NYPosition:int):String
		{
			var EW:int=NXPosition-XPosition;
			var SN:int=NYPosition-YPosition;
			if(EW==1&&SN==1)
			{
				return CompassDirection.NE;
			}
			if(EW==1&&SN==0)
			{
				return CompassDirection.E;
			}
			if(EW==1&&SN==-1)
			{
				return CompassDirection.SE;
			}
			if(EW==0&&SN==1)
			{
				return CompassDirection.N;
			}
			if(EW==0&&SN==-1)
			{
				return CompassDirection.S;
			}
			if(EW==-1&&SN==1)
			{
				return CompassDirection.NW;
			}
			if(EW==-1&&SN==0)
			{
				return CompassDirection.W;
			}
			if(EW==-1&&SN==-1)
			{
				return CompassDirection.SW;
			}
			return "wrong";
		}
	}
}